//
//  剑指Offer 53-1 在排序数组中查找数字I.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/8/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class SolutionSord53 {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let first = findFirst(nums, target: target)
        let last = findLast(nums, target: target)
        if first <= last,
           first >= 0,
           last >= 0,
            last < nums.count,
            nums[first] == target,
            nums[last] == target
        {
            return last - first + 1
        }
        return 0
    }
    func findFirst(_ nums: [Int], target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var ans = -1
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] == target {
                // 如果找到了，先记录下来，继续在左边找
                right = mid - 1
                ans = mid
            } else {
                right = mid - 1
            }
        }
        return ans
    }
    func findLast(_ nums: [Int], target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var ans = -1  // 这个的初始化容易出错
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] == target {
                // 已经找到了，先记录下来，继续在右边找
                left = mid + 1
                ans = mid
            } else {
                right = mid - 1
            }
        }
        return ans
    }
    
    static func test() {
        let solution = SolutionSord53()
        let nums = [5,7,7,8,8,10]
        let target = 8
        let result = solution.search(nums, target)
        print(result)
    }
}
